The subject matter of this invention involves computing systems, and more particularly, a parallel configured adder circuit for use in such computing systems.
Computing systems must include adders to perform regular addition and subtraction. Such adders are typically designed by first developing Boolean equations from which the adders are implemented. Unless these equations are properly modified using certain "minimization" techniques, the adder, resulting from these Boolean equations, experiences an unacceptable delay, in performing regular addition and regular subtraction. In addition, such adders do not perform byte addition and byte subtraction as well as regular addition and regular subtraction.
A traditional formulation of the addition function is described in sections 3.8 and 3.9 of a book entitled "Computer Arithmetic Principles, Architecture, and Design", by Kai Hwang, pages 84-91. This formulation depends, delay-wise, on two paths: (1) one that produces the half sums and (2) one that produces the carries. The recursive formulas are: EQU SUMi=Hi V Ci+1 EQU Ci=Gi+TiCi+1
This formulation is extremely slow because it requires Hi, which is an immediate computation, and Ci+1, which depends on the calculation of the previous carry (Ci+2).
A better solution, using the same formulation, can be achieved using the carry look ahead (CLA) technique, also described in the above mentioned book by Kai Hwang. However, while this solution is an improvement over the traditional formulation mentioned above, the carry still lies on the critical path. The SUM can be computed either implicitly or explicitly. The SUM is computed implicitly by producing a carry propagating from a previous group of bits and using a formulation for the SUM that involves that carry. The SUM is computed explicitly by producing the carry in the particular bit position and using an exclusive-OR to produce the SUM. Implicit calculations will produce the SUM in one additional stage after producing the carry into that group; and the explicit calculations will produce the SUM in two stages after the production of the carry into a group. The critical path, delay-wise, is due to the production of the carries. The SUM requires at least one stage after the creation of the appropriate carry, for either implicit or explicit calculation. In addition, if other requirements are imposed on the addition, as for example, byte addition and/or byte subtraction, the previously described formulation must be appropriately changed. If this has to be done, a carry must be provided for the byte boundaries (not for an arbitrary group of bits) which may not be the most convenient choice, delay-wise; the carry equation must be expanded so as to include the conditions required for masking and/or setting the carry; the SUM equations may need to be changed to respect the needed operations; and additional delay may be added to the critical path. To improve the delay necessary to calculate the SUM, critical quantities must be produced that require less delay than the carries; and the SUM must be produced in such a way so as to require Boolean expressions that can be implemented with the same or less delay as for the traditional formulation.